The present invention relates to data representations of geographic features in a geographic database and more particularly, the present invention relates to a method for determining geographic feature association between the geographic features of one geographic database and the geographic features of another geographic database.
A geographic database contains data that represents some of the physical features in a geographic region. Located in the geographic region are physical features, such as road networks, points of interest (including businesses, municipal facilities, etc.), lakes, rivers, railroads, municipalities, etc. The road network includes, among other things, roads and intersections located in the geographic region. Each road in the geographic region is composed of one or more road segments that represent a portion of the road. Generally, the geographic database that represents the geographic region contains at least one database record (also referred to as xe2x80x9centityxe2x80x9d or xe2x80x9centryxe2x80x9d) for each road segment in the geographic region.
The need to establish an association between geographic features represented in one database with the geographic features represented in another database arises in various applications relating to the use of the data representations of the geographic features. Some of these applications include measuring geographic database accuracy, detecting geographic database changes and geographic database conflation. For instance, measuring geographic database accuracy evaluates how closely a representation of the geographic features (e.g., sampled road segments) match the actual geographic features (e.g., ground truth road segments).
One method for associating the geographic features of two geographic databases is to visually identify which geographic feature of a second geographic database most likely corresponds to one of the geographic features of a first geographic database. Typically, a map containing the graphical representation of the geographic features of the first database for a particular region is plotted over a map containing the graphical representation of the geographic features of the second database for the same region. If a geographic feature of the first geographic database is at a similar location and has a similar shape as a geographic feature of the second geographic database, for example, the two features nearly overlap, the two features are selected as being associated. This visual identification of the associated feature pairs is performed over the entire plotted region. Furthermore, this visual identification process needs to be performed for each of the numerous geographic regions represented in the databases which can be very time consuming and labor intensive.
Accordingly, there exists a need for an improved way to determine an association between the geographic features of two geographic databases.
To address these and other objectives, the present invention includes a method of determining geographic feature association between geographic features of a first geographic database and a second geographic database. An mxc3x97n proximity matrix G is built comprising a proximity value element for each of the m features of the first geographic database compared to each of the n features of the second geographic database. A singular value decomposition of the proximity matrix G is computed into a form G=TDUT where T is an mxc3x97m orthogonal matrix, U is an nxc3x97n orthogonal matrix, and D is a mxc3x97n diagonal matrix having a plurality of diagonal elements. The singular value decomposition is converted into an association matrix P by forming a matrix E by replacing each of the diagonal elements of the diagonal matrix with one and computing the association matrix P using the following product P=TEUT. An associated feature pair is identified. The associated feature pair comprises the feature in the first geographic database and the feature of the second geographic database that is a largest element in both one of the rows and one of the columns of the association matrix P.